package magneticCave;

import java.util.Iterator;
import java.util.ListIterator;
import java.util.Random;
import java.util.LinkedList;
import java.util.HashMap;

public class Globals
{

	//Makes a move if it can
	public static boolean MakeMove(int[] grid, int row, int col, int color)
	{
		//check to see if the spot doesn't already have something in it.
		if(grid[(row * Leaf.ROWS) + col] == 0)
		{
			//we can place here if we're at the left or right side of the board.
			if(col == 0 || col == Leaf.COLS -1) 
			{
				grid[(row * Leaf.ROWS) + col] = color;
				return true;
			}
			else
			{
				//if not on the sides,  check to see if we're adjacent to another piece
				if((grid[(row * Leaf.ROWS) + col-1] != 0 )||//check left
					(grid[(row * Leaf.ROWS) + col+1] != 0) ||//check right
					(row != 0 && grid[((row -1) * Leaf.ROWS) + col] != 0 ) || //check up
					(row != Leaf.ROWS-1 && grid[((row+1) * Leaf.ROWS) + col] != 0)) //check down	
				{
					grid[(row * Leaf.ROWS) + col] = color; //make a move
					return true;
				}
				else
					return false;
			}
		}
		else
			return false;
	}
	
	
	public static Leaf GenerateTree(int depth, int[] gridConfig, int firstPlayer)
	{
		Leaf curLeaf = new Leaf(firstPlayer);
		curLeaf.grid = gridConfig;
		return RecGenTree(1, curLeaf, depth, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	
	public static Leaf RecGenTree(int curDepth, Leaf leaf, int maxDepth, int alpha, int beta)
	{
		
		//check for a win. If this is a winning condition, there's no point in continuing
		int winner = Globals.CheckForWinner(leaf.grid);
		if(winner == Leaf.BLACK)
		{
//			if(leaf.getPlayer() == Leaf.BLACK) //last player was white, so this is a really bad move for white (don't ask how this could happen)
//				leaf.SetValue(Integer.MAX_VALUE - 10000);
//			else
			leaf.SetValue(Integer.MAX_VALUE); //last player was black, so this is a really good move for black
			
			
			return leaf;
		}
		else if(winner == Leaf.WHITE)
		{
//			if(leaf.getPlayer() == Leaf.WHITE) //last player was black, so this is a really bad move for black  (don't ask how this could happen)
//				leaf.SetValue(Integer.MAX_VALUE - 10000);
//			else
			leaf.SetValue(Integer.MIN_VALUE); //last player was white, so this is a really good move for white
			
			return leaf;
		}
		
		//stop condition
		if(curDepth >= maxDepth)
		{
			//evaluate the current node
			leaf.SetValue(Globals.Evaluate(leaf.grid, leaf.getPlayer()));
			return leaf;
		}
		

		//toggle color, so the next move will be for the next player
		int nextColor = Leaf.NO_ONE;
		if(leaf.getPlayer() == Leaf.BLACK)
			nextColor = Leaf.WHITE;
		else
			nextColor = Leaf.BLACK;
		
		
		boolean maximizing = (leaf.getPlayer() == Leaf.BLACK);
		int bestUtility = maximizing ?  Integer.MIN_VALUE : Integer.MAX_VALUE;
		boolean stop = false;
		
		Leaf lastBestChild = null;
		
		for(int i = 0; i < Leaf.ROWS && !stop; i++)
		{
			for(int j = 0; j < Leaf.COLS && !stop; j++)
			{	
				int[] grid = leaf.grid.clone(); //copy grid
				//if a move can be made, add it to the list
				if(MakeMove(grid, i, j, leaf.getPlayer()))
				{
					//make a new node, for the opponent 
					Leaf newleaf = new Leaf(grid, nextColor, i, j);										
					//generate your child
					leaf.AddNode(RecGenTree(curDepth+1, newleaf, maxDepth, alpha, beta));
					
					
					//Alpha-beta Pruning & minimax - pass down the alpha or beta value to the other children.
					if(maximizing && newleaf.GetValue() > alpha)
					{
						alpha = newleaf.GetValue();
						
						if(alpha > beta)
						{   //cutoff - stop generating children
							bestUtility = beta;
							leaf.SetBestChild(lastBestChild);
							stop = true;
							continue;
						}
						else 
						{
							bestUtility = alpha;
							leaf.SetBestChild(newleaf);
						}
					}
					else if(!maximizing && newleaf.GetValue() < beta)
					{
						beta = newleaf.GetValue();
						
						if(alpha > beta) { //stop generating children
							bestUtility = alpha;
							leaf.SetBestChild(lastBestChild);
							stop = true;
							continue;
						}
						else
						{
							bestUtility = beta; //my best move
							leaf.SetBestChild(newleaf);
						}
					}
					leaf.SetValue(bestUtility);
					lastBestChild = newleaf;
				}
			}
				
		}
		return leaf;
	}
	
	// color = player color: BLACK or WHITE
	//recursively generates the tree. Called in GenerateTree
//	public static Leaf RecGenTree(int curDepth, Leaf leaf, int maxDepth)
//	{
//		if(curDepth >= maxDepth)
//		{
//			Random rand = new Random();
//			 //generate a value between -10 and 10 for the last leaf
//			int randval = rand.nextInt(11);
//			int neg = rand.nextInt(2);
//			if(neg == 1)
//				randval *= -1;
//			leaf.SetValue(randval);
//			
//			return leaf;
//		}
//		
//
//		//toggle color, so the next move will be for the next player
//		int nextColor = 0;
//		if(leaf.getPlayer() == Leaf.BLACK)
//			nextColor = Leaf.WHITE;
//		else
//			nextColor = Leaf.BLACK;
//		
//		for(int i = 0; i < Leaf.ROWS; i++)
//		{
//			for(int j = 0; j < Leaf.COLS; j++)
//			{	
//				int[] grid = leaf.grid.clone(); //copy grid
//				//if a move can be made, add it to the list
//				if(MakeMove(grid, i, j, leaf.getPlayer()))
//				{
//					//make a new node
//					Leaf newleaf = new Leaf(grid, nextColor);										
//					leaf.AddNode(RecGenTree(curDepth+1, newleaf, maxDepth));
//					
//				}
//			}
//		}
//		return leaf;
//	}
	
	
	
	
	public static int CheckForWinner(int[] grid)
	{
		int numConsecBlack = 0;
		int numConsecWhite = 0;
		for(int row = 0; row < 8; row++)
		{
			for(int col = 0; col < 8; col++)
			{
				if(grid[(row * Leaf.ROWS) + col] != 0)
				{	
					if(grid[(row * Leaf.ROWS) + col] == Leaf.BLACK)
					{
						numConsecBlack++;
						numConsecWhite = 0;
						if(numConsecBlack >= 5)
							return Leaf.BLACK;
					}
					if(grid[(row * Leaf.ROWS) + col] == Leaf.WHITE)
					{
						numConsecWhite++;
						numConsecBlack = 0;
						if(numConsecWhite >= 5)
							return Leaf.WHITE;
					}
				}
				else 
				{
					numConsecBlack = 0;
					numConsecWhite = 0;
				}
			}
			
		}
		
		numConsecBlack = numConsecWhite = 0;
		
		//check vertical
		for(int col = 0; col < 8; col++)
		{
			for(int row = 0; row < 8; row++)
			{
				if(grid[(row * Leaf.ROWS) + col] != 0)
				{	
					if(grid[(row * Leaf.ROWS) + col] == Leaf.BLACK)
					{
						numConsecBlack++;
						numConsecWhite = 0;
						if(numConsecBlack >= 5)
							return Leaf.BLACK;
					}
					if(grid[(row * Leaf.ROWS) + col] == Leaf.WHITE)
					{
						numConsecWhite++;
						numConsecBlack = 0;
						if(numConsecWhite >= 5)
							return Leaf.WHITE;
					}
				}
				else 
				{
					numConsecBlack = 0;
					numConsecWhite = 0;
				}
			}
		}
		//check diagonals
		int winner = Leaf.NO_ONE;
		if((winner = CheckDiag(grid, 3, 0, 7, 4)) != Leaf.NO_ONE)
			return winner;
		if((winner = CheckDiag(grid, 0, 1, 6, 7)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 0, 0, 7, 7)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 1, 0, 7, 6)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 2, 0, 7, 5)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 3, 0, 7, 4)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 0, 1, 6, 7)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 0, 2, 5, 7)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 0, 3, 4, 7)) != Leaf.NO_ONE)
			return winner;
		
		
		if((winner = CheckDiag(grid, 0, 4, 4, 0)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 0, 5, 5, 0)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 0, 6, 6, 0)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 0, 7, 7, 0)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 1, 7, 7, 1)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 2, 7, 7, 2)) != Leaf.NO_ONE)
			return winner;
		
		if((winner = CheckDiag(grid, 3, 7, 7, 3)) != Leaf.NO_ONE)
			return winner;
		
		
		return Leaf.NO_ONE;
		
	}
	
	protected static int CheckDiag(int[] grid, int sx, int sy, int endX, int endY)
	{
		int colInc= 0;
		int rowInc = 0;
		if(sx > endX)
			colInc = -1;
		else
			colInc = 1;
		
		if(sy > endY)
			rowInc = -1;
		else
			rowInc = 1;
		
		int numConsecBlack = 0;
		int numConsecWhite = 0;
		while(sx < Leaf.COLS && sy < Leaf.ROWS && sx >= 0 && sy >= 0)
		{
			
			if(grid[(sy * Leaf.ROWS) + sx] != 0)
			{	
				if(grid[(sy * Leaf.ROWS) + sx] == Leaf.BLACK)
				{
					numConsecBlack++;
					numConsecWhite = 0;
					if(numConsecBlack >= 5)
						return Leaf.BLACK;
				}
				else if(grid[(sy * Leaf.ROWS) + sx] == Leaf.WHITE)
				{
					numConsecWhite++;
					numConsecBlack = 0;
					if(numConsecWhite >= 5)
						return Leaf.WHITE;					
				}
	
				
			}
			else
			{
				numConsecWhite = 0;
				numConsecBlack = 0;
			}
			
			sx += colInc;
			sy += rowInc;
		
		}
		return Leaf.NO_ONE;
		
	}
	
	enum States{ON_A_LINE, NOT_ON_A_LINE, SEARCHING}
	//Evaluate the value of the value of the grid for both players.
	public static int Evaluate(int[] grid, int whoseTurn)
	{
		LinkedList<PotentialLine> whiteList = new LinkedList<PotentialLine>();
		LinkedList<PotentialLine> blackList = new LinkedList<PotentialLine>();
		
		
		//get all rows
		for(int i=0; i < Leaf.ROWS; i++)
		{
			CheckLine(grid, 0, i, Leaf.COLS-1, i, blackList, whiteList, whoseTurn);
		}
		//get all columns
		for(int i=0; i < Leaf.COLS; i++)
		{
			CheckLine(grid, i, 0, i, Leaf.ROWS-1, blackList, whiteList, whoseTurn);
		}
		//Get all diagonals
		CheckLine(grid, 3, 0, 7, 4, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 1, 6, 7, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 0, 7, 7, blackList, whiteList, whoseTurn);
		CheckLine(grid, 1, 0, 7, 6, blackList, whiteList, whoseTurn);
		CheckLine(grid, 2, 0, 7, 5, blackList, whiteList, whoseTurn);
		CheckLine(grid, 3, 0, 7, 4, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 1, 6, 7, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 2, 5, 7, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 3, 4, 7, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 4, 4, 0, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 5, 5, 0, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 6, 6, 0, blackList, whiteList, whoseTurn);
		CheckLine(grid, 0, 7, 7, 0, blackList, whiteList, whoseTurn);
		CheckLine(grid, 1, 7, 7, 1, blackList, whiteList, whoseTurn);
		CheckLine(grid, 2, 7, 7, 2, blackList, whiteList, whoseTurn);
		CheckLine(grid, 3, 7, 7, 3, blackList, whiteList, whoseTurn);
		
		//take care of colliding lines, where the collision means that 
		//two imaginary pieces end up forming two lines, when they shouldn't.
		CropLines(blackList);
		CropLines(whiteList);
		
		int totalVal = 0;  
		//compute the final value.
		for(Iterator it = blackList.iterator(); it.hasNext();)
		{
			PotentialLine line = (PotentialLine)it.next();
			totalVal += line.GetValue();
		}
		for(Iterator it = whiteList.iterator(); it.hasNext();)
		{
			totalVal -= ((PotentialLine)it.next()).GetValue();
		}
		
		return totalVal;
	}
	
	static void CropLines(LinkedList<PotentialLine> list)
	{
		//int[] idxdel = new int[list.size()]; //deletion indices
	//	int i = 0;
		LinkedList<PotentialLine> itemsToDelete = new LinkedList<PotentialLine>();
		for(ListIterator<PotentialLine> it = list.listIterator(); it.hasNext(); )
		{
			PotentialLine ln = (PotentialLine) it.next();
			int res = 0;
			//int j = i+1;
			for(Iterator it2 = list.listIterator(it.nextIndex()); it2.hasNext();)
			{
				PotentialLine ln2 = (PotentialLine)it2.next();
				res = ln.Collide(ln2);
				if(res == 1)
				{
					itemsToDelete.add(ln);
				}
				else if(res == 2)
				{
					itemsToDelete.add(ln2);
				}
			//	j++;
			}
			//i++;
		}
		
		for(Iterator it = itemsToDelete.iterator(); it.hasNext();)
		{
			list.remove((PotentialLine)it.next());
		}
	}
	
	
	//checks a line for potential winning lines. Returns 1 or 2 lines, one belonging to white, another to black
	//blackLine & whiteLine = out parameters
	
	private static void CheckLine(int[] grid, int startX, int startY, final int endX, final int endY, 
			LinkedList<PotentialLine> outBlackList, LinkedList<PotentialLine> outWhiteList, int whoseTurn)
	{
		int colInc, rowInc;
		if(startX < endX)
			colInc=1;
		else if(startX > endX)
			colInc=-1;
		else
			colInc = 0;
		
		if(startY < endY)
			rowInc=1;
		else if(startY > endY)
			rowInc=-1;
		else
			rowInc = 0;
		
		int lineFlags = 0;
		int pieceFlags = 0;
	
		if(rowInc != 0 && colInc != 0){
			pieceFlags |= Piece.DIAGONAL;
			lineFlags |= PotentialLine.DIAGONAL;
		}
		int col= startX;
		int row= startY;
		//used to search within the line
		int iendX = startX + (colInc * 4);
		int iendY = startY + (rowInc * 4);
		if(colInc > 0 && iendX >= Leaf.COLS)
			iendX = Leaf.COLS-1;
		else if(colInc < 0 && iendX < 0)
			iendX = 0;
		if(rowInc > 0 && iendY >= Leaf.ROWS)
			iendY = Leaf.ROWS - 1;
		else if(colInc < 0 && iendX < 0)
			iendY = 0;
		
	
		PotentialLine line = new PotentialLine(lineFlags, Leaf.NO_ONE, whoseTurn);
	
		boolean done = false;
		int bestBlack = 0;
		int bestWhite = 0;
		PotentialLine blackLine = null;
		PotentialLine whiteLine = null;
	//	boolean firstColor = true;
		
		while(!done)
		{
			int piece = grid[(row * Leaf.ROWS) + col];//get the piece at this location
			
			//encountered a new colored piece, possibly breaking the current line
			if(piece != 0 && piece != line.GetColor() && line.GetColor() != Leaf.NO_ONE)
			{
				//its not the same color that we were working with before (if any)
				//so this is the start of a new line
				if(line.size() >= 5)
				{
					//fill out the rest of the line
					PotentialLine.GetSurroundingBlanks(line, grid, col, row, rowInc, colInc);
			//		firstColor = true;
					//Only one line per color is allowed on each row/column or diagonal
					//Take only the best.
					if(line.GetColor() == Leaf.BLACK && line.GetValue() > bestBlack)
					{
						blackLine = line;
						bestBlack = line.GetValue();
					}
					else if(line.GetColor() == Leaf.WHITE && line.GetValue() > bestWhite)
					{
						whiteLine = line;
						bestWhite = line.GetValue();
					}
						
					line = new PotentialLine(lineFlags, piece, whoseTurn);	
					
					
					//go back and search again, by one offset, to see what other combinations of 5 we can make
					startX += colInc;
					startY += rowInc;
					col = startX;
					row = startY;
				
					iendX += colInc;
					iendY += rowInc;

					if(iendX == endX && iendY == endY)
						done = true;
					
					continue;
				}
				else 
				{
					//a new color interrupted our line, so start a new one starting from this square
					startX = col; 
					startY = row;
					line = new PotentialLine(lineFlags, Leaf.NO_ONE, whoseTurn);
					line.AddPiece(col, row, pieceFlags, piece, grid);
				}			
			}
			else
			{
				//add whatever's there, be it a blank space or a piece. 
				//we always like to collect more than 5 squares, so we know if 
				//the line is double-ended or not (meaning that it has whites on both sides, and is contiguous)				
				if(piece == Leaf.BLACK || piece == Leaf.WHITE)
					line.AddPiece(col, row, pieceFlags, piece, grid);
				else
					line.AddPiece(col, row, pieceFlags | Piece.IMAGINARY, piece, grid);
								
				//we've got a full line, fill it out
				if(line.size() == 5)
				{					
					if(line.GetColor() != Leaf.NO_ONE)
					{
						PotentialLine.GetSurroundingBlanks(line, grid, col, row, rowInc, colInc);
						if(line.GetColor() == Leaf.BLACK && line.GetValue() > bestBlack)
						{
							blackLine = line;
							bestBlack = line.GetValue();
						}
						else if(line.GetColor() == Leaf.WHITE && line.GetValue() > bestWhite)
						{
							whiteLine = line;
							bestWhite = line.GetValue();
						}						
					}

					
					//reset the line
					line = new PotentialLine(lineFlags, Leaf.NO_ONE, whoseTurn);
				//	firstColor = true;
					col = startX;
					row = startY;
					startX += colInc; //move the start and end points over
					startY += rowInc;
					
					//move the end point over
					iendX += colInc;
					iendY += rowInc;
					//if it passes the boundary, then there are less than 5 squares left, so quit.
					if(((colInc > 0 && iendX > endX) || (colInc < 0 && iendX < endX)) ||
						((rowInc > 0 && iendY > endY) || (rowInc < 0 && iendY < endY)))
					{
						done = true;
						continue;
					}
				}	
								
			}

			//move forward
			col += colInc; 
			row += rowInc;

			
			//see if we've reached the end
			if(col == endX && row == endY)
			{
				if(line.size() >= 5)
				{
					if(line.GetColor() == Leaf.BLACK && line.GetValue() > bestBlack)
					{
						blackLine = line;
						bestBlack = line.GetValue();
					}
					else if(line.GetColor() == Leaf.WHITE && line.GetValue() > bestWhite)
					{
						whiteLine = line;
						bestWhite = line.GetValue();
					}					
				}
				done = true;
			}
		}//end while	
		
		if(blackLine != null)
			outBlackList.add(blackLine);
		if(whiteLine != null)
			outWhiteList.add(whiteLine);

	}//end function
}